package com.yanceysong.codetop.s51_s60;

public class S56_Hard_41_缺失的第一个正数 {
    /**
     * .S56_Hard_41_缺失的第一个正数
     * .<p>
     * .<a href="https://leetcode.cn/problems/first-missing-positive/">LeetCode 41. 缺失的第一个正数</a>
     * .<p>
     * .题目描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * .你需要实现时间复杂度 O(n) 且仅使用常数级额外空间的算法。
     * .<p>
     * .核心标签：数组 / 原地哈希 / 索引映射 / 常数空间 / 探测标记
     * .<p>
     * .关键结论：答案一定在区间 [1, n + 1] 之间（n = 数组长度）。
     * .原因：
     * .- 如果 1..n 全部出现，则最小缺失正数是 n+1；
     * .- 否则缺失的那个数一定落在 1..n 范围内。
     * .<p>
     * .示例：
     * .输入：nums = [1,2,0]   输出：3
     * .输入：nums = [3,4,-1,1] 输出：2
     * .输入：nums = [7,8,9,11,12] 输出：1
     * .输入：nums = [1,1] 输出：2
     * .<p>
     * .思路总览（原地标记法，使用数组自身当布尔存在表）：
     * .1. 过滤阶段：把所有 <=0 或 >n 的数统一改成一个“哨兵值” (n+1)，因为这些值对 1..n 的存在性没有影响。
     * .2. 标记阶段：再次遍历，对每个值 v ∈ [1, n] 在下标 (v-1) 位置做“出现过”标记。标记方式：令该位置的数变成负数（保留其绝对值）。
     * .   由于我们只关心是否出现，不关心次数，取绝对值之后再取负即可避免重复标记的干扰。
     * .3. 扫描阶段：再次遍历，找到第一个值仍为正的下标 i，对应的缺失正数即为 i+1。
     * .4. 如果 1..n 都被标记（都为负），那么返回 n+1。
     * .<p>
     * .ASCII 过程演示： nums = [3, 4, -1, 1]
     * .原始:          [ 3,  4, -1,  1]  n=4  有效目标值范围 [1..4]
     * .过滤后:        [ 3,  4,  5,  1]  (-1 被替换为 5 = n+1)
     * .标记 v=3 -> 下标2: [ 3,  4, -5,  1]
     * .标记 v=4 -> 下标3: [ 3,  4, -5, -1]
     * .标记 v=1 -> 下标0: [-3, 4, -5, -1]
     * .（值 4 在标记时会使下标3负，但已负保持）
     * .扫描：下标0负(出现1)，下标1正(未出现2) => 答案 2
     * .<p>
     * .关键洞察：利用“数值范围受限”的特性，把出现性信息编码进原数组的符号位，避免额外空间。
     * .<p>
     * .复杂度分析：
     * .时间：O(n) 三次线性扫描。
     * .空间：O(1) 只用常数变量，原数组原地修改。
     * .<p>
     * .边界与测试要点：
     * .- 全部连续：如 [1,2,3] -> 4
     * .- 缺第一个：如 [2,3,4] -> 1
     * .- 有负数/零：如 [-1,-2,0] -> 1
     * .- 重复值：如 [1,1] -> 2
     * .- 空数组：[] -> 1 （n=0 时返回 1）
     */
    public int firstMissingPositive(int[] nums) {
        // 数组长度 n
        int n = nums.length;

        // ================== 阶段 1：过滤无关数据 ==================
        // 目标：把所有不可能影响答案的值（<=0 或 >n）替换为统一的哨兵值 n+1
        // 原因：我们只关心 1..n 的出现性；n+1 不会被后续当作有效标记对象。
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1; // 设置为哨兵值
            }
        }

        // ================== 阶段 2：原地标记出现性 ==================
        // 遍历数组，对于每个数组的元素的“有效值” v (1 <= v <= n)，在其映射位置 v-1 上做出现标记。
        // 标记策略：将该位置的值改为负数（保留其绝对值），负号即“出现过”。
        for (int i = 0; i < n; i++) {
            int currentVal = Math.abs(nums[i]); // 取绝对值以防之前已经被标记成负数
            if (currentVal >= 1 && currentVal <= n) {
                int idxToMark = currentVal - 1; // 将值 v 映射到下标 v-1
                // 将映射位置置为负数表示对应的数值出现过；保持绝对值不变可以避免重复写入影响其它标记。
                nums[idxToMark] = -Math.abs(nums[idxToMark]);
            }
        }

        // ================== 阶段 3：寻找首个缺失正数 ==================
        // 再次遍历：第一个保持正数的下标 i 表示 i+1 在数组中是没未出现，也就是不存在的。
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) { // 若为正，说明 i+1 没被标记到
                return i + 1;
            }
        }
        // 若全部为负，说明 1..n 均出现，答案是 n+1
        return n + 1;
    }

    // ================== 测试驱动 ==================
    public static void main(String[] args) {
        S56_Hard_41_缺失的第一个正数 solution = new S56_Hard_41_缺失的第一个正数();
        System.out.println("=== 缺失的第一个正数 测试开始 ===\n");

        // 基础示例
        runTest(solution, new int[]{1, 2, 0}, 3, "基础示例 1");
        runTest(solution, new int[]{3, 4, -1, 1}, 2, "基础示例 2");
        runTest(solution, new int[]{7, 8, 9, 11, 12}, 1, "基础示例 3");
        runTest(solution, new int[]{1, 1}, 2, "重复值");

        // 多重复 & 混合
        runTest(solution, new int[]{2, 2, 2, 2, 1}, 3, "多重复包含 1");
        runTest(solution, new int[]{2, 2}, 1, "两个重复缺 1");

        // 空 / 全非正
        runTest(solution, new int[]{}, 1, "空数组");
        runTest(solution, new int[]{-1, -2, -3}, 1, "全为非正");

        // 完整连续 / 缺首元素
        runTest(solution, new int[]{1, 2, 3}, 4, "连续 1..n");
        runTest(solution, new int[]{2, 3, 4}, 1, "缺失 1");

        // 乱序 / 逆序
        runTest(solution, new int[]{4, 3, 2}, 1, "逆序缺 1");
        runTest(solution, new int[]{5, 4, 3, 2, 1}, 6, "乱序完整");

        // 缺中间值
        runTest(solution, new int[]{1, 2, 3, 5, 6, 7}, 4, "缺中间值 4");
        runTest(solution, new int[]{1, 2, 4, 5, 6}, 3, "缺中间值 3");

        // 缺靠近末尾值
        runTest(solution, new int[]{1, 2, 3, 4, 6}, 5, "缺靠近末尾值 5");
        runTest(solution, new int[]{1, 2, 3, 4, 5, 7}, 6, "缺靠近末尾值 6");

        // 包含超大值干扰
        runTest(solution, new int[]{1000, 1, 2, 3}, 4, "含超大值干扰");
        runTest(solution, new int[]{100, -100, 2, 1}, 3, "混合超大与负值");

        // 前缀完整
        runTest(solution, new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 11, "前缀完整");

        // 全集出现
        runTest(solution, new int[]{2, 1, 4, 6, 3, 5, 8, 7}, 9, "1..8 全部出现");

        // 缺一个靠后但非末尾 (缺 10)
        runTest(solution, new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 11}, 10, "缺值 10");

        // 大值重复与缺失 (缺 4)
        runTest(solution, new int[]{4, 4, 4, 1, 2, 3}, 5, "重复大值且全集出现 1..4");

        // 随机顺序缺第一个(1)
        runTest(solution, new int[]{3, 5, 2, 4}, 1, "随机顺序缺 1");

        // 包含所有 1..n (n=8) + 干扰值 > n
        runTest(solution, new int[]{1, 2, 3, 4, 5, 6, 7, 8, 100, 200}, 9, "全部出现附带干扰值");

        // 单元素场景
        runTest(solution, new int[]{1}, 2, "单元素为 1");
        runTest(solution, new int[]{2}, 1, "单元素不为 1");
        runTest(solution, new int[]{-5}, 1, "单元素负数");

        // 多干扰与缺中间
        runTest(solution, new int[]{-1, 4, 2, 7, 8, 3, 10}, 1, "缺 1 且有干扰");
        runTest(solution, new int[]{-1, 1, 4, 2, 7, 8, 3, 10}, 5, "缺 5 且有干扰");

        // 全部缺 1..n except n+1 (只含超过范围值)
        runTest(solution, new int[]{99, 100, 101}, 1, "全部无效值");

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .统一的测试执行辅助方法。
     * .会复制一份原数组用于展示，避免原地修改后输出现象迷惑。
     */
    private static void runTest(S56_Hard_41_缺失的第一个正数 solution, int[] input, int expected, String title) {
        int[] original = input.clone(); // 保留原始内容用于打印
        int actual = solution.firstMissingPositive(input); // 调用算法（原地修改 input）
        System.out.printf("[%s] 原始: %s -> 结果: %d (期望: %d)%n", title, arrayToString(original), actual, expected);
        assert actual == expected : String.format("测试失败：期望 %d 实际 %d", expected, actual);
    }

    // 简单的数组转字符串工具（避免引入额外库）
    private static String arrayToString(int[] arr) {
        if (arr.length == 0) return "[]";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append(',');
        }
        sb.append(']');
        return sb.toString();
    }
}
